package com.labuladong.sort;

public class Sort {

    // 选择排序
    void selectSort1(int[] nums) {
        int n = nums.length;
        // sortedIndex 是一个分割线
        // 索引 < sortedIndex 的元素都是已排序的
        // 索引 >= sortedIndex 的元素都是未排序的
        // 初始化为 0，表示整个数组都是未排序的
        int sortedIndex = 0;
        while (sortedIndex < n) {
            // 找到未排序部分 [sortedIndex, n) 中的最小值
            int minIndex = sortedIndex;
            for (int i = sortedIndex + 1; i < n; i++) {
                if (nums[i] < nums[minIndex]) {
                    minIndex = i;
                }
            }
            // 交换最小值和 sortedIndex 处的元素
            int tmp = nums[sortedIndex];
            nums[sortedIndex] = nums[minIndex];
            nums[minIndex] = tmp;

            // sortedIndex 后移一位
            sortedIndex++;
        }
    }

    // 对选择排序进行第一波优化，获得了稳定性
    void selectSort2(int[] nums) {
        int n = nums.length;
        int sortedIndex = 0;
        while (sortedIndex < n) {
            // 在未排序部分中找到最小值 nums[minIndex]
            int minIndex = sortedIndex;
            for (int i = sortedIndex + 1; i < n; i++) {
                if (nums[i] < nums[minIndex]) {
                    minIndex = i;
                }
            }

            // 交换最小值和 sortedIndex 处的元素
            // int tmp = nums[sortedIndex];
            // nums[sortedIndex] = nums[minIndex];
            // nums[minIndex] = tmp;

            // 优化：将 nums[minIndex] 插入到 nums[sortedIndex] 的位置
            // 将 nums[sortedIndex..minIndex] 的元素整体向后移动一位
            int minVal = nums[minIndex];
            // 数组搬移数据的操作
            for (int i = minIndex; i > sortedIndex; i--) {
                nums[i] = nums[i - 1];
            }
            nums[sortedIndex] = minVal;

            sortedIndex++;
        }
    }

    // 对选择排序进行第二波优化，获得稳定性的同时避免额外的 for 循环
    // 这个算法有另一个名字，叫做冒泡排序
    void bubbleSort1(int[] nums) {
        int n = nums.length;
        int sortedIndex = 0;
        while (sortedIndex < n) {
            // 寻找 nums[sortedIndex..] 中的最小值
            // 同时将这个最小值逐步移动到 nums[sortedIndex] 的位置
            for (int i = n - 1; i > sortedIndex; i--) {
                if (nums[i] < nums[i - 1]) {
                    // swap(nums[i], nums[i - 1])
                    int tmp = nums[i];
                    nums[i] = nums[i - 1];
                    nums[i - 1] = tmp;
                }
            }
            sortedIndex++;
        }
    }

    // 进一步优化，数组有序时提前终止算法
    void bubbleSort2(int[] nums) {
        int n = nums.length;
        int sortedIndex = 0;
        while (sortedIndex < n) {
            // 加一个布尔变量，记录是否进行过交换操作
            boolean swapped = false;
            for (int i = n - 1; i > sortedIndex; i--) {
                if (nums[i] < nums[i - 1]) {
                    // swap(nums[i], nums[i - 1])
                    int tmp = nums[i];
                    nums[i] = nums[i - 1];
                    nums[i - 1] = tmp;
                    swapped = true;
                }
            }
            // 如果一次交换操作都没有进行，说明数组已经有序，可以提前终止算法
            if (!swapped) {
                break;
            }
            sortedIndex++;
        }
    }

    // 对选择排序进一步优化，向左侧有序数组中插入元素
    // 这个算法有另一个名字，叫做插入排序
    void insertionSort(int[] nums) {
        int n = nums.length;
        // 维护 [0, sortedIndex) 是有序数组
        int sortedIndex = 0;
        while (sortedIndex < n) {
            // 将 nums[sortedIndex] 插入到有序数组 [0, sortedIndex) 中
            for (int i = sortedIndex; i > 0; i--) {
                if (nums[i] < nums[i - 1]) {
                    // swap(nums[i], nums[i - 1])
                    int tmp = nums[i];
                    nums[i] = nums[i - 1];
                    nums[i - 1] = tmp;
                } else {
                    break;
                }
            }
            sortedIndex++;
        }
    }

    // 希尔排序
    void shellSort(int[] nums) {
        int n = nums.length;
        // 初始间隔为数组长度的一半，然后逐渐缩小间隔
        int h = n / 2;
        while (h >= 1) {
            for (int sortedIndex = h; sortedIndex < n; sortedIndex++) {
                // 插入排序过程
                for (int i = sortedIndex; i >= h; i -= h) {
                    if (nums[i] < nums[i - h]) {
                        // swap(nums[i], nums[i - h])
                        int tmp = nums[i];
                        nums[i] = nums[i - h];
                        nums[i - h] = tmp;
                    } else {
                        break;
                    }
                }
            }
            h /= 2;
        }
    }

}
